package com.captain.leetcode2.链表;

import com.captain.leetcode.链表.ListNode;
import org.w3c.dom.NodeList;

public class 重排链表143 {
    public static void main(String[] args) {

        new 重排链表143().reorderList(ListNode.getInstance());
    }

    void reorderList(ListNode head) {
        //1.找到中间点 2.反转再融合

        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到中间值
        ListNode back = slow.next;
        //反转链表
        back = reverse(back);

        slow.next = null;
        ListNode pre = head;

        int n = 1;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (pre != null || back != null) {
            int num = n % 2;
            //奇数 pre链表
            if (num != 0) {
                cur.next = pre;
                pre = pre.next;
                //偶数back链表
            } else {
                cur.next = back;
                back = back.next;
            }
            cur = cur.next;
            n++;
        }
        head = dummy.next;
    }

    public ListNode reverse(ListNode head) {
        if (head == null) return null;
        // 1  2 3 4
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }

}
